package com.xiaoyu.doublePointer;

import java.util.Arrays;

/**
 * @program: DS_and_A
 * @description: 移动0
 *
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 *
 * 输入: [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 *
 * 说明:
 * 必须在原数组上操作，不能拷贝额外的数组。
 * 尽量减少操作次数。
 *
 * @author: YuWenYi
 * @create: 2021-05-25 11:44
 **/
public class MoveZeroes_283 {

    //思路:把所有的非0数字按其原来的顺序都移动到前面,那么剩下的0不就全在后面吗?
    public static void moveZeroes(int[] nums) {
        int slow = 0;  //记录最左边非0位置的索引,一但交换过,那么其就+1,此时说明一个非0数已经在它应该出现的位置上了!
        int temp;
        for (int fast = 0; fast < nums.length; fast++) {
            //快指针去找非0数,然后与慢指针指向的0进行交换就行了
            //为什么一定能确保slow指针的地方是一个0? 因为如果slow不是0,就会跟fast一起移动
            if (nums[fast] != 0){
                //优化,如果slow==fast的时候,说明两个数都不是0,这个时候就不需要交换,
                //直接移动slow指针和fast指针就行了,继续往后面找
                if (slow < fast){
                    temp = nums[fast];
                    nums[fast] = nums[slow];
                    nums[slow] = temp;
                }
                slow++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1,0,0,1,0,3,12,16};
        moveZeroes(nums);
        System.out.println(Arrays.toString(nums));
    }
}
